package com.yww.leetcode.hashtable;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @author yww
 * @description 3. 无重复字符的最长子串
 * @since 2024/2/22 10:51
 */
public class LengthOfLongestSubstring3 {

    // 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
    public int lengthOfLongestSubstring(String s) {
        return lengthOfLongestSubstring2(s);
    }

    /*
    [(a,3) (b,1) (c,2)]

     b
       e
    abcabcbb
    要点：
        1.用 begin 和 end 表示子串开始和结束位置
        2.用 hash 表检查重复字符
        3.从左向右查看每个字符, 如果:
         - 没遇到重复字符，调整 end
         - 遇到重复的字符，调整 begin
         - 将当前字符放入 hash 表
        4.end - begin + 1 是当前子串长度
     */
    public int lengthOfLongestSubstring1(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int begin = 0;
        int maxLength = 0;
        for (int end = 0; end < s.length(); end++) {
            char c = s.charAt(end);
            if (map.containsKey(c)) { // 重复调整begin
                begin = Math.max(begin, map.get(c) + 1);
                map.put(c, end);
            } else {
                map.put(c, end);
            }
            maxLength = Math.max(maxLength, end - begin + 1);
        }
        return maxLength;
    }

    /**
     * s 由英文字母、数字、符号和空格组成，可以由数组进行优化 在 0 ~127 之内
     */
    public int lengthOfLongestSubstring2(String s) {
        int[] map = new int[128];
        Arrays.fill(map, -1);
        char[] chars = s.toCharArray();
        int begin = 0;
        int maxLen = 0;
        for (int end = 0; end < chars.length; end++) {
            char c = chars[end];
            if (map[c] != -1) { // 重复，调整begin
                begin = Math.max(begin, map[c] + 1); // 不能让begin往回走
                map[c] = end;
            }
            map[c] = end;
            maxLen = Math.max(maxLen, end - begin + 1);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        new LengthOfLongestSubstring3().lengthOfLongestSubstring("abca");
    }
}
